package com.rui.study.algorithm.P_零杠一背包_回溯解法;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-12-28 17:43
 **/
public class Solution {

    private int[] items;        // 物品重量

    private int w;              // 背包承重
    private int maxW;           // 求解的最大值
    private boolean[][] memery; // 备忘录

    public Solution(int[] items, int w) {
        this.items = items;
        this.w = w;
        this.memery = new boolean[items.length][w + 1];
    }

    /**
     * 回溯法，其实就是穷举搜索法。
     * “0-1背包”是回溯法求解的经典案例。物品只有两种状态，要么放入背包，要么不放入背包。
     * @param i     考察第几个物品
     * @param cw    当前重量
     */
    public void retrive(int i, int cw) {
        if (cw == w || i == items.length) {          // 当前重量达到最大或者没有物品可以考察了
            if (cw > maxW)
                maxW = cw;
            return;
        }
        if (memery[i][cw])            // 重复状态
            return;
        memery[i][cw] = true;         // 记录(i, cw)这个状态
        retrive(i + 1, cw);                         // 第i个物品不放入
        if (cw + items[i] <= w) {
            retrive(i + 1, cw + items[i]);          // 第i个物品放入
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution(new int[]{3, 4, 5, 7, 8}, 10);
        solution.retrive(0, 0);

        System.out.println("成功求解- [" + solution.maxW + "]");
    }

}
